COMMENT ⊗   VALID 00037 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00004 00002	\input macros[pap,rpg]
C00005 00003	\paper:Issues of Separation in Function Cells and Value Cells.
C00006 00004	\sect Introduction
C00009 00005	\sect Notation and Terminology 
C00018 00006	\sect Historical Perspective
C00025 00007	\sect Technical Arguments
C00030 00008	\ssect Multiple Denotations for a Single Name
C00036 00009	\ssect Referential Clarity
C00038 00010	\ssect Compiler Simplicity
C00043 00011	\ssect Higher Order Functions
C00044 00012	\ssect Abstraction Sharing
C00045 00013	\ssect Multiprocessing
C00047 00014	\ssect Number of Namespaces
C00054 00015	\ssect Macros and Name Collisions
C00063 00016	\ssect The Benefits of Macros
C00067 00017	\ssect Possible Solutions to the Macro Name Collision Problem
C00080 00018	\ssect Space Efficiency
C00084 00019	\ssect Time Efficiency
C00090 00020	\ssect Special Variables
C00092 00021	\sssect Global Versus Special Variables
C00099 00022	\sssect A Third Approach to Special Variables
C00101 00023	\ssect Compatibility Issues
C00105 00024	\sssect Changing Existing Code
C00108 00025	\sssect Compatibility Packages
C00117 00026	\ssect Standardization
C00118 00027	\sect Non-Technical Arguments
C00119 00028	\ssect The Scheme Community
C00125 00029	\ssect The EuLisp Community
C00128 00030	\ssect The Japanese Community
C00129 00031	\ssect The Community of Small Computer Users
C00131 00032	\ssect The Common Lisp Community
C00133 00033	\ssect Can Vendors Afford the Merger?
C00136 00034	\ssect Can Users Afford the Merger?
C00139 00035	\sect Summary
C00140 00036	\sect Acknowledgments
C00141 00037	\sect References
C00145 ENDMK
C⊗;
\input macros[pap,rpg]
\input verbat[pap,rpg]
\magnification\magstep1
\tolerance=2500
\def\lispone/{$\hbox{\bf Lisp}↓1$}
\def\lisptwo/{$\hbox{\bf Lisp}↓2$}
\def\lispfive/{$\hbox{\bf Lisp}↓5$}
\def\lispsix/{$\hbox{\bf Lisp}↓6$}


\paper:Issues of Separation in Function Cells and Value Cells.
\vskip .5truein
\centerline{Richard P. Gabriel}
\vskip .3truein
\centerline{Kent M. Pitman}

\sect Introduction

In 1981 the emerging Common Lisp \ref:Steele.1984. community turned to
Scheme for some of its motivation and inspiration. Adopting lexical
scoping proved one of the most important decisions the Common Lisp group
ever made.

One aspect of Scheme that was left behind, however, was a unified
namespace for functions and values, and accompanying uniform evaluation
rules for expressions in function and argument positions within the
language.  At the 1986 ACM Conference on Lisp and Functional Programming,
members of the European community involved in the design of a dialect
called Eulisp raised the issue that perhaps Common Lisp should have
adopted this paradigm and that perhaps it would still be appropriate to do
so.

Many people in the Common Lisp community were not happy about the proposed
change. Technical, philosophical, and political arguments on both sides of
the issue became quickly apparent. Since this issue has been seen to be
controversial, the Common Lisp community felt it important to clearly
document both sides in an unbiased way before attempting to make any
decision on the subject.

Scheme and Eulisp have chosen to adopt a unified namespace. Several questions
remain to be answered:

\numitem{$\bullet$} Is it technically desirable for the Common Lisp community
to change?

\numitem{$\bullet$} Is it politically desirable for the Common Lisp community
to change?

\numitem{$\bullet$} Will the Common Lisp community choose to change?

To an extent, the issue to be decided may not be simply whether the
function and value namespaces in Common Lisp will merge, but perhaps also
a larger issue of whether any of the several several Lisp
communities---Common Lisp, Scheme, and Eulisp---can or should eventually
merge.

\sect Notation and Terminology 

We will begin by establishing some standard terminology for use within
the context of this paper. The impatient reader may wish to skip this 
section and refer back to it only if he or she has a question about some term
that he or she does not understand.

A {\bf function} is anything that may correctly be given to the
\smcp{FUNCALL} or \smcp{APPLY} function and is to be executed as code when
arguments are supplied.  A {\bf non-function} is any other lisp object.

An {\bf identifier} is the name of a symbol or a variable; this is not 
an exclusive partition.  An identifier is essentially a print name.

A {\bf symbol} is a Lisp data structure that has a value cell, 
a function cell, a property list, and so on.

A {\bf variable} is an identifier that names a location.

A {\bf binding} is a pairing of an identifier with a location in which
location a Lisp object may be placed.

A {\bf lexical variable} is a binding in which the identifier is not
taken to refer to a symbol.
A symbol with a value in its value cell is taken to be a binding in that
the name of the symbol is paired with the value cell of the symbol. 
A {\bf special variable} is a binding in which the identifier {\it is} taken
to refer to a symbol. 

An {\bf environment} is the set of all bindings in existence at some given time.
We will call a subset of an environment a {\bf sub-environment}.

A {\bf namespace} is a sub-environment. Often the location parts of the
bindings in a namespace contain objects used for some purpose, and the
identifiers of the namespace are said to `name objects' used for that
purpose; if the types of objects that can be stored in the location parts
of bindings in a namespace are used for a purpose such that only objects
of a certain type can be used for that purpose, then we say that `the
objects in the namespace are restricted' to that type of object.  The
objects that are stored in the location parts of bindings in a namespace
are not necessarily restricted to first-class Lisp objects.  In this white
paper, there are two namespaces of concern, which we will term the `value
namespace' and the `function namespace.' Other namespaces include tag
names (used by \smcp{TAGBODY} and \smcp{GO}) and block names (used by
\smcp{BLOCK} and \smcp{RETURN-FROM}), but the objects in the location
parts of their bindings are not first-class Lisp objects.

The {\bf value namespace} is a sub-environment whose location parts are not
restricted to any particular kind of object. The binding of
an identifier referring to a symbol along with a value cell is in the
value namespace.  Lexical variables, such as those introduced by \smcp{LET}, 
\smcp{LAMBDA}, and \smcp{MULTIPLE-VALUE-BIND}, are in the value namespace.  

The {\bf function namespace} is a sub-environment whose location parts 
are restricted to functions, except under error conditions.
The binding of an identifier referring to a symbol along with a 
function cell is in the function namespace. Functional lexical variables,
such as those introduced by \smcp{FLET}, \smcp{LABELS}, and \smcp{MACROLET}, 
are in the function namespace.

Lisp's evaluation rules tell, given an expression and an environment, how
to produce a value or values and a new environment. In order to do this,
the meanings of identifiers in a program text need to be determined, and
this requires determining in which namespace to interpret the identifiers.
For example, a symbol can have something in its value cell and something
else in its function cell; which of these objects is referred to by the
symbol in a piece of code depends upon which namespace is defined to be
used for the context in which the symbol appears.

The Common Lisp specification defines that it is an error to place a
non-function in the function cell of a symbol. Since this is a discussion
of correct programs, it should be assumed in all objects placed in the
function cell of a symbol are valid functions unless specifically stated
otherwise.

The function and value namespaces are distinct in Common Lisp because,
given a single name, the function namespace mapping and the value
namespace mapping can yield distinct objects. The two mappings
{\it might} yield the same object, but that would be mere coincidence.

For the purposes of this document, we may wish to refer to two abstract 
dialects of Lisp, which we shall call \lispone/ and \lisptwo/.

\lispone/ has a single namespace, which serves a dual role as the function
namespace and value namespace. That is, its function namespace and value
namespace are not distinct. In \lispone/, the functional position of a form
and an argument positions of forms are evaluated according to the same rules.
Scheme \ref:Rees.1986. and Eulisp \ref:Padget.1986. are \lispone/ dialects.

\lisptwo/ has distinct function and value namespaces. In \lisptwo/, the
rules for evaluation in the functional position of a form are distinct from
those of evaluation in the argument positions of the form.
Common Lisp is a \lisptwo/ dialect.

\sect Historical Perspective

Historically, most Lisp dialects have adopted a two-namespace approach to
the naming problem. Largely this is because most dialects followed Lisp 1.5
\ref:McCarthy.1965. unless there was some interesting reason not to follow it,
or else they have chosen to follow dialects derived from Lisp 1.5.

Lisp 1.5 broke symbols into values and functions; values were stored on an
association list, and functions on the property lists of symbols.
Compiled and interpreted code worked differently from each other.  In the 
interpreter, the association list was where all bindings were kept.  When 
an identifier was encountered (an `atomic symbol' in Lisp 1.5 terminology), 
it was taken to be a variable to be evaluated for its value. First the 
\smcp{APVAL} part of the symbol was interrogated---an \smcp{APVAL} was ``{\bf A}
{\bf P}ermanent, system-defined {\bf VAL}ue'' stored in a specific place in 
the symbol. Second, the association list was searched. Finally, if neither 
of these other two possibilities found a binding, an error was signalled.

When a combination was encountered, the function position was evaluated
differently from the other positions. First, the symbol was interrogated
to see whether there was a function definition associated with the symbol,
then the association list was searched.

Here we can see two namespaces at work, though non-symbol variables (Lisp
1.5 did not have lexical variables in interpreted code) were treated
somewhat uniformly: when there were no function definitions associated with
a symbol, there was one namespace, explicitly represented by the association 
list.

Compiled code worked a little differently, and from its internals
we can see where the two namespaces came about in descendants from
Lisp 1.5, at least conceptually.

The Lisp 1.5 compiler supported `common' and `special' variables. 
A common variable enabled compiled and interpreted code to communicate
with each other. A common variable was bound on an explicit association 
list, and to evaluate such a variable a call to \smcp{EVAL} was emitted to 
determine the value.  A special variable was the compiler's modeling 
of free variables and closely matched what is called today `shallow 
binding.'  Ordinary variables were compiled into what we have termed
`lexical variables.'

Thus, we see all of the components of the two-namespace world in Lisp
1.5, along with some of the components of the one-namespace world.

The designers of Lisp 1.5 seem to have thought of function names differently
from variable names---the Lisp 1.5 interpreter looks at the property list
of the named atomic symbol first, and so it can be argued that a function
was considered a property of a function. The designers used the terminology
that a symbol `stands for' a function, while a variable `refers' to
a value.

Lisp for the PDP-6 at MIT adopted the style of the Lisp 1.5 special
variables for dynamic binding in both compiled and interpreted code,
eliminating common variables. Compilers were still written to try to
interpret special variables as lexical variables in as many places as
possible. The value of a symbol was stored in the special value cell of
the symbol and the function remained on the property list as it did in
Lisp 1.5.

At MIT MacLisp was a direct descendent of the PDP-6 Lisp, and it continued
on with the tradition of being a \lisptwo/. InterLisp followed even more
closely in the footsteps of Lisp 1.5 than did MacLisp, and it also kept
the tradition alive.

Vax NIL is a descendent of MacLisp, intended to be the Lisp for the Vax in
which Macsyma could be written. Macsyma code makes strong assumptions
about running in a Lisp with two namespaces, so it did not make sense to
collapse the namespaces in Vax NIL, even if the possibility ever was
raised.

S-1 Lisp is simply a dialect of NIL for the S-1 Mark IIA, and so it is a
\lisptwo/.  Spice Lisp is an intellectual descendent of MacLisp, so it
followed tradition.  ZetaLisp, for whatever reasons, became a \lisptwo/.

Common Lisp was a compromise among a number of dialects of Lisp, most of
them descendents of MacLisp, all of them \lisptwo/s. A major aspect of the
Common Lisp movement was compromise along political lines.

\sect Technical Arguments

\ssect Notational Simplicity

Many people believe that having the function position be evaluated
differently from the argument positions in \lisptwo/ is very inelegant.
The reason that different evaluation rules are needed is because
there are different namespaces or environments for function bindings
and for value bindings. Therefore there is an evaluation rule for
each environment.  

\lisptwo/ is slightly more complicated in situations where we want 
to do either of the following two actions:

\numitem{$\bullet$} Fetch the value of an identifier in the value namespace
and call it as a function.

\numitem{$\bullet$} Fetch the value of an identifier in the function
namespace pass it around as a value.

To use the value of an identifier in the value namespace as a function,
\lisptwo/ provides this notation:

\begintt
(FUNCALL <identifier> . <arguments>)
\endtt

\noindent For example, in \lisptwo/ one might write

\begintt
(DEFUN MAPC-1 (F L) (DOLIST (X L) (FUNCALL F X)))
\endtt

\noindent In \lispone/, one would write

\begintt
(DEFUN MAPC-1 (F L) (DOLIST (X L) (F X)))
\endtt

To use the value of an identifier in the function namespace as a
normal value, \lisptwo/ provides this notation:

\begintt
(FUNCTION <identifier>)
\endtt

\noindent which is often abbreviated as simply 

\begintt
#'<identifier>
\endtt

\noindent For example, in \lisptwo/ one might write

\begintt
(MAPC #'PRINT '(A B C D))
\endtt

\noindent In \lispone/, one would write

\begintt
(MAPC PRINT '(A B C D))
\endtt

The differences are more striking in a larger, more complex example.
In \lisptwo/, one can write the \smcp{Y} operator as

\begintt
(DEFUN Y (F)
 ((LAMBDA (G) #'(LAMBDA (H) (FUNCALL (FUNCALL F (FUNCALL G G)) H)))
  (LAMBDA (G) #'(LAMBDA (H) (FUNCALL (FUNCALL F (FUNCALL G G)) H)))))
\endtt

\noindent while in \lispone/, one can write

\begintt
(DEFUN Y (F)
 ((LAMBDA (G) (LAMBDA (H) ((F (G G)) H)))
  (LAMBDA (G) (LAMBDA (H) ((F (G G)) H)))))
\endtt

The call to this operator in order to compute $6!$ in \lisptwo/ 
would look like

\begintt
(FUNCALL (Y #'(LAMBDA (FN)
               #'(LAMBDA (X)
                  (IF (ZEROP X) 1 (* X (FUNCALL FN (- X 1))))))) 
         6)
\endtt

\noindent In \lispone/, the same call would look like

\begintt
((Y (LAMBDA (FN)
     (LAMBDA (X)
      (IF (ZEROP X) 1 (* X (FN (- X 1)))))))
 6)
\endtt

Some argue that the \lispone/ form is easier to read because it is more concise.
Others feel that the \lisptwo/ form is easier to read because the use of functions
whose names are not constant are clearly marked.

It would not surprise us to find that the question of which is easier to
read is strongly correlated to the frequency with which a given programmer
actually passes functions as arguments or uses passed arguments functionally.
If this is an uncommon event, it is probably useful to have the incident
flagged visually. If this is a common event, the additional notation may 
quickly become cumbersome.

\ssect Multiple Denotations for a Single Name

Some people find it less confusing to have a single meaning for a name.
Fewer meanings mean less to remember.

For example, suppose a programmer has defined a function \smcp{F} as

\begintt
(DEFUN F (X) (+ X 1))
\endtt

\noindent Then suppose the programmer is writing a new function \smcp{G} and
wants it to take a functional parameter \smcp{F} which it is to apply
to its other argument.  Suppose the programmer writes

\begintt
(DEFUN G (F) (F 3))
\endtt

Issues of defined program semantics aside, it's probably obvious that the
programmer who wrote this piece of code meant to call the function named
by the formal parameter \smcp{F} on the argument \smcp{3}.  In \lisptwo/,
however, this function will ignore its argument named \smcp{F} and simply
invoke the globally defined function named \smcp{F} on 3.  Notice,
by the way, that this is precisely what Lisp 1.5 would have done.

Unfortunately, not all situations are as clear cut as this. For example, 
consider the following:

\begintt
(DEFUN PRINT-SQUARES (LIST)
  (DOLIST (ELEMENT LIST)
    (PRINT (LIST ELEMENT (EXPT ELEMENT 2)))))
\endtt

\noindent In this definition, there are three uses of the name
\smcp{LIST}. The first is in the function's formal parameter list. The
second is in initialization of the \smcp{DOLIST} variable. The third is in
the \smcp{PRINT} expression. This program, which is valid in current
Common Lisp, would not be valid in \lispone/ because the name LIST could not
simultaneously denote a list of numbers and a function. In \lispone/, a
common thing to write instead would be

\begintt
(DEFUN PRINT-SQUARES (LST)
 (DOLIST (ELEMENT LST)
   (PRINT (LIST ELEMENT (EXPT ELEMENT 2)))))
\endtt

\noindent In the function \smcp{PRINT-SQUARES}, the parameter named \smcp{LST} is
better named \smcp{LIST}.

As should be clear from these examples, the advantage of treating the
function and argument positions the same is that using parameters as
functions is made more convenient syntactically.

The disadvantage is that {\it not} using parameters as functions is made
less convenient syntactically, because parameter names must be more
carefully chosen in order to not shadow the names of globally defined
functions that will be needed in the function body.

Of course, care in naming must already be observed in order to assure
that variable names chosen for some inner binding construct not shadow
the names of variables bound by outer binding constructs. For example,
consider:

\begintt
(DEFUN HACK-LIST (LIST)
  (LET ((LST (HACK-LIST LIST)))
    (HACK-SOME-MORE LIST LST)
    (SHUFFLE LIST LST)))
\endtt

\noindent There are two variables that could naturally be named `LIST,'
and the programmer must chose which one to so name.

Nevertheless, the degree of care required to avoid name
collisions in \lispone/ is can be theoretically no less than that required
in \lisptwo/, but has been statistically observed to be far more, a point to
which we will return later.

The following is a simple example of some of the important issues 
in variable naming:

\begintt
(DEFUN ODDITY (LIST) (LIST LIST LIST))
(ODDITY #'CONS)
\endtt

\noindent Depending on which way the issue is decided, the possible return
values from this function might be

\begintt
(#<SUBR CONS> . #<SUBR CONS>)
(#<SUBR CONS> #<SUBR CONS>)
\endtt

\ssect Referential Clarity

In \lisptwo/, without knowing the context, it is not possible to decide 
whether the function or the value namespace is the proper one to use.
These two forms result in different interpretations of an expression, {\it x}:

$$(x\ldots)$$

$$(\ldots x\ldots)$$

A basic `rule' of Lisp style is that code is clearest when 
the least amount of context is necessary to determine what each 
expression does. Unfortunately, that rule is violated in \lisptwo/.

In a presentation at the 1986 ACM Conference on Lisp and Functional
Programming, Steele complained that the $\alpha$ operator in 
Connection $\hbox{Machine}↑\copyright$
\ref:Steele.1986., which he wanted to implement as a simple readmacro,
was not possible to implement as he desired because of this
context problem. The problem is that the $\alpha$ operator needed to
expand differently depending on whether it was expanding in a 
functional or argument position. In \lispone/, this problem would
not have arisen. However, the problem could be solved in \lisptwo/
by introducing `lambda macros' such as those which are already
used in Zetalisp \ref:Symbolics.1986b..

\ssect Compiler Simplicity

In current Common Lisp compilers, special case code is used when
deciding which namespace mapping to use when a variable is examined
by the compiler. 

The maintainers of some Common Lisp compilers claim that a change
from \lisptwo/ to \lispone/  semantics would result in simpler, 
smaller, faster compilers. One reason for this is that knowledge 
about which namespace is in effect at any given time is often
procedurally embedded.  By merging the two namespaces, the same
pieces code can be used in more places, reducing the overall
number of places where such information is represented and ultimately
making the maintenance task simpler.

The maintainers of other Common Lisp compilers claim, however, that
a change from \lisptwo/ to \lispone/ semantics would reduce the 
complexity of their compilers little if at all---that it might
force small changes at points distributed throughout the system, 
but that overall the  compiler would not change very much.

There is some concern, however, that the overall complexity of compilers
might increase as a result of such a change. This belief is based on the
observation that the change effectively causes type information to be
lost. Specifically, for \lisptwo/ a compiler writer can assume that whatever
is in a symbol-function cell must be a function; for \lispone/ a compiler
writer cannot assume that, if a programmer has written an expression that
invokes a function associated with a symbol, that the contents of the
symbol-value cell of that symbol will be a function when the function
invocation is performed.

In some cases, this information may be recoverable, but the compiler may
have to perform extensive type inference to do so.  Often, the compiler
will have to take an unnecessarily conservative approach.

Consider a function such as

\begintt
(DEFUN F (X) (G X))
\endtt

\noindent Even in this simple function, we are assuming that

\begintt
(SYMBOL-FUNCTION 'G)
\endtt

\noindent is a function. When a good compiler is directed to compile safe
code, that compiler must concern itself with the question of whether this
cell will ever contain a non-function. For some computers, if the compiler
cannot show that the contents of the symbol-function cell is always a
function, then it must generate less efficient code.

Compilers can be written assuming that symbol-function cells always
contain functions in \lisptwo/ because it is legal to forbid non-functions
from ever being placed in the symbol-function cell. For example, Vax~Lisp
\ref:Digital.1986. does this. Consequently, the Vax~Lisp compiler can safely
generate code that simply jumps to the contents of the value cell of
\smcp{G}.  In \lispone/, however, this is not possible without
introducing new declarations.

The bottom line here is not that some compilers are better than 
others, but rather that compilers may vary widely in their nature,
and, as such, the effects of the proposed change may have widely
varied effects depending upon the implementation.

\ssect Higher Order Functions

While functions, like \smcp{Y}, that directly manipulate
other functions are possible to write in either \lispone/ or \lisptwo/,
many programmers feel that \lispone/ allows one to write them more
perspicuously.  The point is that the more cumbersome notation of
\lisptwo/ does nothing to encourage and may even discourage the 
writing of such functions.

\ssect Abstraction Sharing

In \lispone/ it is easier to define an abstract piece of code that shares
abstractions between data and functions. An example of this is the
abstract stream code in Chapter 4 of \ref:Abelson.1985., in which it is
shown how to write streams based either on functions or on data
structures.  Again, all of this is possible in \lisptwo/, but it is not an
encouraged style. The problem is that it is a burden to think about which
namespace will be used for various variables.

\ssect Multiprocessing

The functional programming style has been seen to be conducive to
multiprocessing.  That is, the functional style of programming results in
programs that are more easily rendered into a parallel style. For
evidence of this, look at typical Common Lisp programs and contrast their
style and suitability for parallelization with the same programs as they
might be written in Scheme.

By transitivity, then, since \lispone/ tends to better encourage functional 
programming style, \lispone/ is also more conducive to multiprocessing.

Of course, Common Lisp is not designed to accomodate multiprocessing and
it would take more than a unification of the function and value
namespaces to allow Common Lisp to support multiprocessing in any
serious way. At this time, integrated support of multiprocessing has not
been established as an explicit goal of Common Lisp. Nevertheless, it
seems apparent that experience with a more functional programming style
will provide a good foundation for programmers who later move to a
language that does support multiprocessing in an integrated way, so
this issue should not be overlooked.

\ssect Number of Namespaces

There are really a larger number of namespaces than just the two being
discussed here. As we noted earlier, other namespaces include at least
those of blocks and tags, and types names and declaration names are often
considered namespaces.  As such, the names \lispone/ and \lisptwo/ that we
have been using are slightly misleading.  The names \lispfive/ and
\lispsix/ might be more appropriate.

This being the case, the unification the function and value namespaces
does not accomplish as much as it might initially appear to do.  Even with
that change, the interpretation of a symbol in a Common Lisp program would
still depend on the context to disambiguate variables from symbols from
type names and so on.

On the other hand, some proponents of the change have suggested that, in
time, these other namespaces would be collapsed as well. Dialects of
Scheme have done this---some to a greater extent than others.   The hope
is that with when all namespaces are reduced to a single one that
that there will be a simple evaluation rule for identifiers.

In fact there are an arbitrary number of namespaces because of the
existence of functions like \smcp{GET}, \smcp{ASSOC}, and \smcp{GETHASH},
which allow users to effectively associate new kinds of information with
symbols.  Even if the underlying Lisp supports exactly one namespace,
programmer will be able to invent other namespaces for their own
use. The effect of reducing the number of namespaces in the Lisp to
one will help programmers keep track of their own namespaces, but
the ``one identifier, one meaning'' motto will not necessarily apply to user
code.

Earlier, an argument was presented that might have left the impression
that because a \lispone/ compiler can be simpler than a \lisptwo/ compiler
there was some implied simplicity of \lispone/ over \lisptwo/.  But the
fact that compilers for a Lisp of one namespace complexity is more or less
complicated than a compiler for a Lisp of another namespace complexity is
a statement about the level of Lisp compiler technology used in the two
Lisps rather than being a statement about the abstract effect the
differing namespace complexities have.  The truth is that the additional
meanings that can be associated with symbols can and do have a very
powerful effect.

Indeed, much of the power of associative functions like \smcp{GET} derives 
from what amounts to a structured kind of pun---the fact that a single
symbol (or any object, for that matter) may have more than one kind of
information usefully associated with it. The power and importance of 
this kind of structured interplay between arbitrary namespaces is hard
to deny and probably does not warrant the level of disdain that is 
sometimes given it by Scheme enthusiasts.

\ssect Macros and Name Collisions

Macros as they exist in Common Lisp are very close to being semantically
bankrupt. The problem is that they expand into an expression that is
composed of symbols that have no attached semantics. When
substituted back into the program, a macro expansion could conceivably
take on a quite surprising meaning depending on the local environment.

Some symbols that ultimately appear in the expansion of a macro are
obtained, by macro definition, through its parameter list from the macro
consumer. It is therefore possible to use those symbols safely. However,
writers of macros often work on the hypothesis that additional
functional variables may be referenced in macros as if they were globally
constant. Consider the following macro definition:

\begintt
(DEFMACRO MAKE-FOO (THINGS) `(LIST 'FOO ,THINGS))
\endtt

\noindent Here \smcp{FOO} is quoted, \smcp{THINGS} is taken from the
parameter list for the macro, but \smcp{LIST} is free. The writer of this
macro definition is almost certainly assuming either that \smcp{LIST} is
locally bound in the calling environment and is trying to refer to that
locally bound name, or else that \smcp{LIST} is to be treated as constant
and that the author of the code in the calling environment will know to
not locally bind \smcp{LIST}. In practice, the latter assumption is
almost always made.

If the consumer of the above macro definition writes

\begintt
(DEFUN FOO (LIST) (MAKE-FOO (CAR LIST)))
\endtt

\noindent in \lispone/, it is likely that there will be a bug in the code.

Here is another example of code that would be a problem in \lispone/:

\begintt
(DEFMACRO FIRST (LIST) `(CAR ,LIST))
(DEFUN TEST-CAR (CAR TEST-LIST)
  "The `driver' program for Frobozz Automobile, Inc.'s
   quality assurance test."
  (DO ((TESTS TEST-LIST (REST TESTS)))
      ((NULL TESTS))
    (FUNCALL (FIRST TESTS) CAR)))
\endtt

It's worth emphasizing, however, that these problems come up in 
either \lispone/ or \lisptwo/. The issue is really just that they are
statistically more likely in \lispone/ since there is less contextual 
information available to help out. Here is an example of how the problem
arises in normal Common Lisp:

\begintt
(DEFMACRO FOO (X Y) `(CONS 'FOO (CONS ,X (CONS ,Y NIL))))

(DEFUN BAZ (X Y)
 (FLET ((CONS (X Y) (CONS Y X)))
  (FOO X Y)))
\endtt

\fix{(BAZ~1~2)} returns \fix{(((NIL~.~2)~.~1)~.~FOO)}
even though it seems that
\fix{(FOO~1~2)}
might have been intended by the programmer.

Although few implementations support its full generality in file
compilation, a strict reading of the Common Lisp specification seems to
imply that it should be acceptable to write:

\begintt
(DEFMACRO FOO (X Y) ;take a deep breath
  `(FUNCALL ',#'CONS 'FOO (FUNCALL ',#'CONS ,X (FUNCALL ',#'CONS ,Y NIL))))

(DEFUN BAZ (X Y)
  (FLET ((CONS (X Y) (CONS Y X)))
    (FOO X Y)))
\endtt

Here 
\fix{(BAZ~1~2)}
should evaluate to 
\fix{(FOO~1~2)}
just as everyone expected.

Given all of this, the thoughtful reader should ask: Why do macros appear
work as often as they do?

The answer seems to be based primarily in history and statistics and not
in some theoretical foundation. In recent dialects preceding Common
Lisp, such as Maclisp \ref:Pitman.1983., it was fortunately true that there
was no \smcp{FLET}, \smcp{LABELS}, or \smcp{MACROLET}. This meant that there was
an extremely high likelihood that the function bindings of identifiers 
in the macro expander's environment would be compatible with the function 
bindings of the same identifiers in the program environment. Coupled with
the fact that the only free references that most macro expansions tend 
to make are functional, this meant that writers of macros could guess
enough information about how the expansion would be understood that fairly
reliable macro packages could be developed.

With the advent of \smcp{FLET}, \smcp{LABELS}, and \smcp{MACROLET}, the risk of
conflict is considerably higher.  The Scheme community, which has long
had constructs with power equivalent to that of forms \smcp{FLET}, has
never adopted a macro facility into the language. This is because, 
among other things, macros have generally seemed like a semantically
empty concept to many of the Scheme designers. This data is again
supportive of the argument that \lispone/ dialects are more prone to 
name collisions than \lisptwo/ dialects.

The main reason why we have not seen large numbers of problems in Common
Lisp to date may well be that most Common Lisp programmers are still
programming using a Maclisp programming style and using forms like
\smcp{FLET} and \smcp{LABELS} in only very limited ways. Those groups that
do use \smcp{FLET} and \smcp{LABELS} heavily may well be composed of
individuals who learned Lisp with Scheme and do not use macros heavily or
who understand the issues outlined here well and write macros in a
controlled manner.

It should not be surprising to find increasingly many name collision
problems reported by users of Common Lisp macros as time progresses.
A change from \lisptwo/ to \lispone/ semantics for identifiers would
very likely hasten the process.

\ssect The Benefits of Macros

Although macros can be seen to be `semantically bankrupt,' they are at
least pragmatically useful. The concept of semantic bankruptcy is
interesting, because, for example, in a Lisp with \smcp{IF} and
\smcp{PROGN}, the additional semantic power of \smcp{COND} is null, and
so one might think that \smcp{COND} represents a bankrupt construct.
Yet \smcp{COND} buys stylistic improvements to some Lisp code, especially
code that would be indented too far to the right in proper indentation
style or code that would not highlight the relationships of the
conditions being tested by not placing them, vertically, near each other.

Therefore, semantically poor constructs can help programmers organize their
code to be more readable, more maintainable, and to express the abstractions
in their programs in such a way that the code runs efficiently.

Common Lisp programmers are judged on their ability to use macros
appropriately and judicously.  Without the pervasive use of macros, a
modern Lisp programming style would not have been developed, and Lisp as a
mature programming language would have never come about.  Many people
believe that the powerful Lisp macro facility is the main reason that Lisp
has been successful over the years.

Macros can be used to optimize the code produced by examining the
forms passed to the macro definition function, and different code
can be produced depending on the shape of those forms.

Macros can be used to define extensions to Lisp because macros enable
the programmer to define new evaluation rules.

Most programmers simply do not experience the name collision problems
mentioned in the previous section with the frequency that seems to be
appropriate to the depth of the problem, largely because of the existence
of a function namespace.  \smcp{FLET} and \smcp{LABELS} define functions,
and programmers treat function names more carefully than non-function
names.  Therefore, letting function names be freely referenced in a
macro definition is not a big problem.

There are two ways to look at the arguments regarding macros and namespaces.
The first is that a single namespace is of fundamental importance, and therefore
macros are problematic. The second is that macros are fundamental, and therefore
a single namespace is problematic.

\ssect Possible Solutions to the Macro Name Collision Problem

With the problems with macros describe earlier, one would hope that
there could be some solutions to the problem if a \lispone/ were to
become a standard dialect of Lisp.

Recall the following code:

\begintt
(DEFMACRO FIRST (LIST) `(CAR ,LIST))
(DEFUN TEST-CAR (CAR TEST-LIST)
  "The `driver' program for Frobozz Automobile, Inc.'s
   quality assurance test."
  (DO ((TESTS TEST-LIST (REST TESTS)))
      ((NULL TESTS))
    (FUNCALL (FIRST TESTS) CAR)))
\endtt

In some Scheme implementations it is possible to write the following:

\begintt
(DEFMACRO FIRST (LIST) `(',CAR ,LIST))
\endtt

\noindent This is syntactically more tedious but has the obvious advantage
that there is no potential for name confusion. Nevertheless, something
like this doesn't instantly answer all technical problems.  When uses of
this macro are compiled to a file,
one of two things must be output to the file and later read back in:

\numitem{1.}an object such as \smcp{\#$\langle$COMPILED-FUNCTION
CAR$\rangle$}, which is the name of a compiled code object

\numitem{2.}a representation of the compiled code object for \smcp{CAR}.

Lisp and Scheme implementations that can output only 
names of compiled code objects
will need to produce named functions along with references to them
in compiled code files for those functions that are incidentally
defined in macro definitions.
For
example, consider the following, more complex macro definition:

\begintt
(DEFMACRO FOO (N X) `(',(LAMBDA (X) (+ X N)) ,X))
(FOO 3 Z)
\endtt

\noindent The incidental function \fix{(LAMBDA (X) (+ X N))} will need a
name.

For Lisp and Scheme implementations that output representations of code
objects into files, there is an additional problem, which is that for each
use of a macro like \smcp{FOO} there may be a separate copy of the
compiled code for the anonymous function in the macro definition.  Also,
in addition to writing the compiled code to a file, all procedures
necessary to support it must also be correctly saved and restored by the
file compiler.

One problem with outputting code objects to a file is that there is a
possibility of having multiple copies of the same code object in the Lisp
image when the file is loaded.  Some systems are able to collapse
structurally equal compiled-code objects into only one copy when the
occurrences of them are all in a single file, but this requires some
work and does not solve the problem of the same code object appearing
in multiple files.

When the speed of compiled code is important, programmers will wish their
compiler to open-code invocations of Lisp primitives like \smcp{CAR}.
Usually compilers notice such occurrences of \smcp{CAR} by recognizing
occurrences of the symbol \smcp{CAR}.  When macros indicate the invocation
of primitives like \smcp{CAR} and the approach being discussed is in
force, compilers will need to notice occurrences of \smcp{CAR} by
recognizing occurrences of the compiled code object that implements
\smcp{CAR}.  For instance, in the example above, the compiler ought to
open-code the original \smcp{CAR} operation in the \smcp{TEST-CAR} code
rather than to code a function call to \smcp{CAR}.  To do this, the
compiler must be made to understand a new set of idioms, and the size
and complexity of the compiler will possibly grow.

Even when speed of compiled code is not an issue, open coding these idioms
will help in a few cases where a code object would then not have to be
written to a file, but will not help when open coding in not desired by
the programmer either for reasons of space efficiency or modularity.

A proposed solution to the macro problem is presented in \ref:Kohlbecker.1986.,
where the author asserts that macros can be written in a style that
is like the current Common Lisp style, but free function position
variables can be defaultly taken to be the globally defined function of
the same name.

Another partial solution might be to include a new declaration form, which
declares function definitions constant so that Common Lisp implementations
could declare all Common Lisp functions constant. The correct behavior of
a \lispone/ with the built-in functions declared constant would be to signal
an error when cases like \smcp{TEST-CAR} above occur. However, functions
without this declaration would not receive the benefit of this check and
macros that need to use them would continue to be error-prone. Also, it
would be necessary for users to know which names in the language were
constant even if they did not plan to use them for their intended use.  To
such users, these names would appear to be holes in the space of available
names. For example, an automobile manufacturer would likely prefer to use
the name \smcp{FIRST} rather than \smcp{CAR} to access the first element
of a list exactly because the manufacturer would want to recycle the name
\smcp{CAR} for some other purpose. Packages can be used to alleviate some
of these problems, but many view packages as fairly clumsy in their own
right.

Another solution to the macro problem is to eliminate them altogether
and use functions are the abstraction mechanism rather than macros.
The compiler can be directed to inline code the functions that form
the basis for abstraction, gaining speed. The only aspect of macros that
are not as easily modelled this way is the optimization mentioned
earlier.

\ssect Space Efficiency

If a symbol is used both for its value and as a function, it currently
costs no additional space. Any program that has symbols that are used to
denote distinct functions and values, however, would have to be changed.
In general, this means that some new symbols would be introduced. In most
cases, the number of new symbols introduced would not be extremely large,
but there might be pathological applications where there were exceptions.

In the Lucid Lisp system \ref:Lucid.1986., there are 14 of these symbols, and
the value cell is being used, in these cases, as a cache for an object
related to the function. In the MACSYMA system \ref:Symbolics.1986a.
there are roughly 35 out of total of 10,000 of these symbols.

Using the same name to refer to both a function and a value cell can be more
space efficient since it means adding only one additional cell to an existing
data structure that already has on the order of 5 to~10 cells anyway.

This issue can be put quantitatively.  Let $n$ be the number of symbols in
a system, let $S↓2$ be the space occupied by the average symbol in an
implementation of \lisptwo/, let $S↓1$ be the space occupied by the
average symbol in an implementation of \lispone/, and let $x$ be the
number of symbols that must be added to a system to resolve name
conflicts.  Then the space saved by having separate environments is

$$(n+x)S↓1-nS↓2$$

For example, if $n$ is 8000, $x$ is~14, $S↓1$ is~28 (bytes), and 
$S↓2$ is~32 (bytes), then the space saved by \lisptwo/ is $-31608$ (bytes).  
That is, 12\% of the symbol space used by such a \lisptwo/ implementation 
might be saved if it were made to be a \lispone/ implementation instead.
In order for there to be no net change in the amount of storage between
a two-namespace and a one-namespace Lisp, one would need over 1100 symbols
to be added to the system to resolve name conflicts.

This issue is not likely to be a major point of contention.

\ssect Time Efficiency

In \lisptwo/, a function call to a function associated with a symbol
involves indirecting through the symbol's function cell. A typical
implementation on stock hardware will look at the symbol's function cell,
which points to a piece of code, possibly with an intermediate pointer
through a procedure object, as in S-1 Lisp \ref:Brooks.1982.. An
optimization to this is for a function call to jump directly to the
correct code object, perhaps indirecting through a link table of some
sort, but eliminating the indirection through the symbol's function cell.
In order for \smcp{DEFUN} and \fix{(SETF (SYMBOL-FUNCTION...)...)}  to
cause existing running code to call the redefined function, the operation
of changing a symbol's function cell will invalidate the link table or
otherwise cause the correct new link to be made.

To use this same optimization in a single namespace Lisp, \smcp{SETQ},
rather than \fix{(SETF (SYMBOL-FUNCTION...)...)} must do the invalidating
or re-linking.  The common case is that there is not a function associated
with a symbol---programmers do not often write code that changes function
definitions in inner loops---and so it makes sense to define a flag for
each symbol that states whether the symbol-value cell is being used as a
function; then the code executed for \smcp{SETQ} can test this flag to
decide whether to invalidation or re-linking.

Of course, only an assignment to a symbol need to be checked.  The worst
case is that, rather than being open coded, \smcp{SETQ} would become a
function call; in this situation, the speed loss would be from a single
instruction time to up to 30 instruction times.  The expected case is that
a test and branch will be added to \smcp{SETQ}, where \smcp{SETQ} might
have been a single instruction before. On some stock hardware, tricks with
the addressing hardware and word alignment can be played to make this fast
in the non-functional value case, but even with a test-and-branch added to
each \smcp{SETQ} it seems unlikely that this could cause any more than a
10\% degradation in the most pessimistic inner loop, and overall it is
unlikely to cause a very noticeable degradation in any large system.

Some people might be confused by the number and complexity of space and time
tradeoffs being discussed here. First, the reason that the link table
methodology is chosen by Lisp implementors for stock hardware
implementations is that a shorter and faster function calling sequence can
be gained using the link table; usually the objects used to represent
compiled functions in these implementations can be shortened as well.  The
space gained by these shortenings is balanced fairly well with the storage
needed for the link tables. Second, changing from \lisptwo/ to \lispone/
results in a smaller image because of the reduction in the amount of
storage needed for symbols. Third, the additional code needed for testing
assignment of symbols decreases the speed of running code and increases
its size.  Because assignment to symbols is infrequent and because
changing function definitions associated with symbols is rare, the speed
tradeoff probably results in a negligible loss in speed, and the space
tradeoff also probably results in a small space increase.

Also, this issue is an illustration of the earlier claim that simplifying
the surface language might not always result in a simpler implementation
strategy since this is one of several ways in which the implementation might be
forced to be more complicated as a result of such a change.

\ssect Special Variables

If Common Lisp became a \lispone/ dialect, we would need to create a conceptual
distinction between global variables that were lexical and global variables
that were special. Consider the following definitions:

\begintt
(DEFUN PLUS (X Y) (+ X Y))
(DEFUN SOMEWHAT-MORE-THAN (X) (PLUS X *SOMEWHAT*))
\endtt

In \lispone/, there are {\it two} free variable references in the definition
of \smcp{SOMEWHAT-MORE-THAN}---\smcp{*SOMEWHAT*} and \smcp{PLUS}. In fact,
the definition of \smcp{PLUS} references a free variable, which is +.

To avoid a compiler warning for the free use of variables such as
\smcp{*SOMEWHAT*}, it is common in Common Lisp to declare such variables
\smcp{SPECIAL}. In order to have compilers for \lispone/ not warn about
the free use of \smcp{PLUS}, it would be unfortunate for these to have to
be declared \smcp{SPECIAL}.  

There are several approaches to this problem; the next sections address
those solutions.

\sssect Global Versus Special Variables

A free variable in Common Lisp is taken to be a dynamic rather than
a lexical reference. This is because there is no global lexical environment
in Common Lisp. In this code

\begintt
(DEFUN FOO (X)(+ X Y))
\endtt

\noindent the reference to \smcp{Y} is special (dynamic). On the surface,
in \lispone/, the reference to `+' is free also, and so it is special
(dynamic).
 One proposed solution is to make the default be lexical
(global), which makes \smcp{Y} refer to the global value for \smcp{Y}, and
`+' to the global definition of +.

Because the reference to `+' will be to the global definition of +, a
compiler can assume that unless there is a lexical binding for `+' the
global definition can be assumed, and the compiler is free to open code +.
Without the ability to make this assumption, the compiler would not be
guaranteed that there was no special binding of `+' that might dynamically
intervene.

However, whereas before a compiler for \lispone/ would warn about
special references, now the compiler would warn about global references,
though it can produce reasonable code in many cases.

In short, there would be a global lexical environment in which symbols
that are used freely would be accessed. Currently there is a global
dynamic environment.

This further change would require users to modify their code, the
change being to, possibly, add some \smcp{SPECIAL} declarations for
variable references.

\sssect A Second Approach to Special Variables

One approach to this problem would be to introduce a new declaration,
which made a variable (lexically) \smcp{GLOBAL} but not \smcp{SPECIAL}.
When a variable is \smcp{GLOBAL}, its value is taken from the symbol-value
cell whenever that variable is freely referenced.  Bindings of that
variable are lexical, as usual. This is contrasted with \smcp{SPECIAL}
variables, in which free references are to the symbol-value cell or to the
most recent \smcp{SPECIAL} binding of it; thus, bindings of \smcp{SPECIAL}
variables are special, not lexical.  \smcp{DEFUN} would presumably be made
to declare function names \smcp{GLOBAL} implicitly.

Given such a declaration, it would still be possible in a \lispone/ to write
definitions such as:

\begintt
(DEFUN ZAP (FN X Y)
  (LET ((PLUS (LAMBDA (X Y) (MAPCAR PLUS X Y))))
    (LIST (PLUS (FN X) (FN Y)) (PLUS (FN (FN X)) (FN (FN Y))))))
\endtt

\noindent where \smcp{PLUS} is defined above,
without worrying that the \smcp{LET}-binding of \smcp{PLUS} would affect
the argument \smcp{FN}. To explain the issues a little better, we will
number the references to \smcp{PLUS} and show the definition in
a different typeface:

$$\vbox{\settabs\+\cr
\+(&DEFUN ZAP (FN X Y)\cr
\+&(&LET (($\hbox{\bf PLUS}↓1$ (LAMBDA (X Y) (MAPCAR $\hbox{\bf PLUS}↓2$ X Y))))\cr
\+&&(LIST ($\hbox{\bf PLUS}↓3$ (FN X) (FN Y)) ($\hbox{\bf PLUS}↓4$ (FN (FN X)) (FN (FN Y))))))\cr}$$

\noindent $\hbox{\bf PLUS}↓1$ is a lexical binding of the variable named
\smcp{PLUS}; $\hbox{\bf PLUS}↓2$ references the global value of
the symbol \smcp{PLUS}; $\hbox{\bf PLUS}↓3$ and $\hbox{\bf PLUS}↓4$
are lexical references to the binding of $\hbox{\bf PLUS}↓1$. If \smcp{FN}
is bound to a function that is defined like this, for instance,

$$\vbox{\settabs\+\cr
\+(DEFUN BAZ (X) ($\hbox{\bf PLUS}↓5$ X X))\cr}$$

\noindent then $\hbox{\bf PLUS}↓5$ refers to the global value of
\smcp{PLUS} rather than to the \smcp{LET}-bound value in \smcp{FOO}.
If \smcp{DEFUN} were to declare function names \smcp{SPECIAL}, then
$\hbox{\bf PLUS}↓2$ and $\hbox{\bf PLUS}↓5$ would refer to the
\smcp{SPECIAL} binding for \smcp{PLUS}, namely $\hbox{\bf PLUS}↓1$, in
this example.

\sssect A Third Approach to Special Variables

Alternatively, rather than introducing the \smcp{GLOBAL} declaration, we
could simply assert that globally defined functions are constant and that
it is illegal to bind their names.

The new \smcp{GLOBAL} declaration is more flexible, but making existing
implementations understand it correctly would involve more work for
implementors than would the alternate of asserting that globally defined
functions are constant.

Closely related to this issue is the fact that there is currently no
system-provided dynamic variation of \smcp{FLET} and \smcp{LABELS} in
Common Lisp, though in a non-multiprocessing environment they can be
more-or-less simulated by creative use of \smcp{UNWIND-PROTECT}. If
Common Lisp were made a \lispone/ dialect, dynamic functional variables
would be something it would get `for free.' And if their use became
popular, it might be desirable to have two kinds \smcp{DEFUN}---one that
created special definitions and another that created lexical definitions.

\ssect Compatibility Issues

A transition from \lisptwo/ semantics to \lispone/ semantics would
introduce a considerable amount of incompatibility. There is the
question of implementor problems as well as user problems.

\sssect Changing Existing Code

Large bodies of code already exist that make assumptions about the current
semantics. That code would all have to be changed. Users who did not favor
this change would likely resent the amount of work required to make the 
change, which might be non-trivial.

In some cases, mechanical techniques could diagnose which programs needed
to be changed. However, because of the pervasive use of macros and of 
automatic programming techniques, it would not be possible to do such
diagnosis with 100\% reliability in any automatic way.

Compilers could be modified to provide the user information about conflicts
as they come up as a sort of machine-gun approach to the problem. This would
address some problems in automatic programming that could not be detected by
statically examining the code that does such programming.

However, some situations are still more complicated because they do not
directly produce code. Instead, they examine and modify code. For example,
compilers, translators, macros, and code walking utilities may have
built-in assumptions about the number of namespaces; if these assumptions
are never explicitly represented, they might elude automatic techniques,
possibly leading to errors or inefficiencies later on.

\sssect Compatibility Packages

Various compatibility schemes have been proposed that claim to allow these
problems to be eliminated.  For example, we might have a Common Lisp
with \lispone/ semantics with a compiler switch that allows \lisptwo/ code 
to be compiled.  Symbols would have function cells, but possibly represented 
as properties on property lists. All old Common Lisp code of the form:

\begintt
(F ...)
\endtt

\noindent would be transformed to this:

\begintt
(FUNCALL #'F ...)
\endtt

\noindent where \smcp{FUNCTION} would look things up in the `function
cell.' \smcp{FUNCALL} would be retained in the compatibility package. A
bigger example is more convincing:

\begintt
(LET ((LIST ...))
 (LIST ...))
\endtt

\noindent would become

\begintt
(LET ((LIST ...))
 (FUNCALL #'LIST ...))
\endtt

During the transformation process, variables bound by occurrences of
\smcp{FLET} and \smcp{LABELS} in the old code would be renamed to new
names produced by \smcp{GENSYM}, and the \lispone/ versions of \smcp{FLET}
(which is \smcp{LET}) and \smcp{LABELS} would be substituted for the
function namespace versions.

Possibly some compilers already perform this transformation internally and
will be simplified after the change. And perhaps an implementor will want
to provide a real function cell for this compatibility in order to run old
code relatively fast. Lisps that normally have link tables will need to
provide separate linking code (possibly the old link code) for the
compatibility package.

This type of compatibility takes a \lisptwo/ program and produces a
\lispone/ program that uses some compatibility features for \lisptwo/
programs added to the \lispone/. In theory, the \lisptwo/ source for
the transformed program could be thrown away and then only the \lispone/
code with the compatibility features could be used in the future.

Unfortunately, there are several problems with this kind of compatibility.

First, it does not lend itself neatly to mixing compiled and interpreted
code, especially when such code is produced at runtime. It becomes
important, for example, to clearly document and control whether
functions which receive expressions to be evaluated or code-walked or
whatever are receiving expressions in \lispone/ or \lisptwo/. Since this
information is not likely to have been explicitly represented in the
data flow of the original \lisptwo/ program, and since our compatibility
scheme does not introduce new data flow to carry such information,
confusion on this point is inevitable.

Also, the compatibility package could expand expressions into code that
was opaque to certain code walkers, compilers, and macro facilities,
which might have made closed-world assumptions about the kinds of
expressions that were likely to come up in a particular application and
hence the kinds of properties that it would be necessary to show in order
to accomplish correct expansion. The reason that this might occur is that
the proposed translation may involve treating some forms that were documented
as special forms as if they were macros. This would mean that code analysis
routines that were expecting to see a certain class of expressions would in
fact see a different class of expressions that it didn't realize could occur.

Another problem occurs when the compatibility code uses property lists to
hold the `symbol-function' cells and the \lisptwo/ to be translated also
uses them. In this case the running \lispone/ version of the \lisptwo/ code
might destroy part of the compatibility information.

It is clear that there is a class of \lisptwo/ programs that could be
safely run under this translation-style of compatibility. There is
also, clearly, a class of programs that require a stricter compatibility.

A second stage of compatibilty would require, essentially, a complete
implementation of the total semantics of \lisptwo/ along side, but sharing
code from, the \lispone/. For example, a `real' symbol-function cell
would need to be implemented, along with an \smcp{EVAL} and a compiler---the
compiler could be a combination of the translator mentioned above and the
\lispone/ compiler.

Finally, some programs may function correctly but suffer an efficiency
loss that is greater than the simple loss which might be assumed by just
analyzing the theoretical speed of the compatibility code. For example,
suppose a macro would be capable of performing an interesting optimization
if it could prove something about a certain side-effect within a certain
range of code.

A simple compatibility package can probably take care of a certain class of
Common Lisp programs, but for programs that would require, essentially,
an implemenation of \lisptwo/ in \lispone/ for compatibility, it is probably
best to require programmers to translate those programs into \lispone/.

There is a population of Common Lisp programmers who will simply not want
to rewrite their code, and there is a body of Common Lisp code such that
the compatibility schemes require as much work to use as to translate the
code.

\ssect Standardization

In standardizing a language, we should take care to standardize
those things that have had proven success and acceptance by a
user community. It is often dangerous to standarize on the
most recently formulated ideas. The new macro solutions by
Kohlbecker and Clinger reported in here are of this form.

It is very tempting to the get the latest good ideas into
a language, but that is a different situation from getting the
latest good ideas into a standard.

\sect Non-Technical Arguments

\ssect The Scheme Community

With the advent of Common Lisp, the Lisp and Scheme communities have
considerably more overlap than they have ever had in the past.

Compatibility with Scheme is not currently a goal of the Common Lisp
design committee. On the other hand, if all other things were equal, there
would be no reason for us to seek to be gratuitously incompatible with
Scheme.

If Common Lisp were to become a \lispone/ dialect, it might prove
possible to develop a layered definition in which Scheme is the base 
layer and Common Lisp is the `industrial strength' layer. Scheme
might then be a natural subset for use on smaller computers and 
embedded systems.

Of course, the Scheme community would need to be convinced that this
layering is desirable. Though the entire Scheme community has not been
involved in any discussions of the issue, some of its members have
expressed interest in the idea. Without the full support of the Scheme
community, there is no guarantee that Scheme will not later change in an
incompatible way that will coincidentally thwart such a good faith move
on the part of the Common Lisp community. Although Scheme was originally
formed to accomodate a particular set of design features that its
authors found interesting \ref:Sussman.1975., it has survived partially as a
vehicle for experimentation in more `purist' features, which might
directly conflict with the practical needs of an industrial strength
Lisp. In \ref:Rees.1986., for example, it is explicitly stated that Common
Lisp compatibility is not uppermost in the list of concerns of the
Scheme community.  A formal merger, which seems appropriate at the moment,
could later turn sour.

If we did become compatible, we would have to be careful to not constrain
the Scheme community to stick too closely to the particular definition 
of Scheme that would be this fundamental layer. 

On the other hand, the Scheme designers believe that Common Lisp has a
number of bad warts---two namespaces being foremost---and that, therefore,
compatibility is not as important as it would be if the foundations of
each dialect were more closely akin. With the willingness of the Common
Lisp community to `see the light,' perhaps the willingness to remain
compatible with the newer, merged dialects, would be greater.

If compatibility with Scheme is desired, there are other changes to Common
Lisp that are necessary or desirable. Foremost are tail recursive
semantics and \smcp{CALL-WITH-CURRENT-CONTINUATION}, in which first-class
continuations are supported. This change would be completely upwards
compatible and is not conceptually hard to implement; but, there are many
details and so it is not easy to implement.

On the other hand, perhaps the Scheme community would see the willingness
of the Common Lisp community to change one wart as an invitation to 
begin negotiations for eliminating the rest of the warts. In that case
we are engaged in a new language design rather than a standardization
effort.

\ssect The EuLisp Community

A new community of Lisp users has emerged in Europe, rallying around a
dialect of Lisp that they call EuLisp. The EuLisp group is endeavoring 
to define a new standard for Lisp---possibly to be proposed to the ISO
community as a standard for Lisp. 

Their approach seems to be to take lessons primarily from the past rather 
than to try to learn from the designs of contemporary dialects of Lisp.
Rather than building on existing specifications, this group is starting
anew, with all the concomitant social pressures of developing a standard
using a slightly too large working group. Key member of this group are
Jerome Chailloux, Julian Padget, John Fitch, Herbert Stoyan, Giuseppe 
Attardi, and Jeff Dalton.

They wish to propose a 3-level standard. At the lowest level, level~0,
is the minimal Lisp, possibly suitable for proving properties of Lisp
programs. The second level, level~1, is of the size and extent of Scheme
and is intended as the right size for small personal computers.  
The highest level, level~2, is about of the size and extent of Common Lisp.
It is intended as the industrial strength Lisp with a number of as-of-now
unspecified environmental features.

The key differences between EuLisp as it now stands and Common Lisp include
a unified variable namespace, as in \lispone/, and simplified lambda-lists
(which do not allow \smcp{\&OPTIONAL} or \smcp{\&KEY}).

At one face-to-face meeting, Chailloux and Padget stated that if Common
Lisp were to collapse the two namespaces, they might be willing to adopt
fancy lambda-lists. These two concessions are possibly enough to lay the
groundwork for a widespread set of compromises, mostly from them, on the
merger of the two communities.

Without this technical merger, a messy political battle,
unwelcomed by both the Common Lisp and EuLisp communities,
might ensue.

\ssect The Japanese Community

The Japanese community seems to want to stick with Common Lisp pretty much
as it is today, according to reports from Prof. Ida. It appears that there
is a heavy commitment to the current definition in the commercial marketplace
there. The political issue seems to be that we will have a battle at the ISO
level regardless of the decision we make.

\ssect The Community of Small Computer Users

Owners of small computers who would like to run Lisp are effectively 
forced to run Scheme since implementations of Common Lisp for small 
computers are very hard to find.

This makes it appear as if Common Lisp were not designed to meet
commercial needs, because most of the commercial world uses small
computers and hardly any serious Common Lisp implementations have been
attempted even in the face of a potentially large market.

If Scheme or something like it could be incorporated as a subset or
as a fundamental lower level, it might be possible to make an 
interesting subset of Common Lisp available for users of these machines
in a useful way.

On the other hand, the average size of a `small' computer is increasing 
at a brisk pace. By the time any standard is finally approved by ANSI, 
the cost of supporting a `level 3' Common Lisp may not be prohibitive
even on `small' computers, and some argue that that day is already here.

\ssect The Common Lisp Community

The Lisp vendors have, largely, convinced the commercial world that the Lisp
community has decided to get its act together and settle on one dialect of
Lisp---Common Lisp---and that it is time to start writing commercial
products using that dialect. If the Lisp community now changes Common Lisp
in such an incompatible way, the newly-convinced commercial world
might balk.

In addition there are other parts of the Common Lisp community who
have grown to see the warts as beauty marks. For them the changes
to bring these other communities together are gratuitous. We have
to recognize that there are important segments of the Common Lisp
community who will strongly fight this change. As we should not
ignore the European and Japanese Lisp communities, so we should not
ignore the loyal Common Lisp community.

It is possible, of course, that an X3 sanction of such a change as
part of not only a US standard Lisp but an international standard 
Lisp would make it easier for vendors to accept such a change. But 
preliminary feedback from a number of large vendors and large consumers
suggests that some people consider there to already be an informal 
standard, which they would be dismayed to see changed.

\ssect Can Vendors Afford the Merger?

Most Lisp vendors have their hands full improving and honing their
products. Typically these vendors schedule tasks 6 months to a year ahead.
At the very least, if the merger takes $n$ person-months to accomplish for
some vendor, there are $n$ person-months of something else very useful that
does not get done.  If the task of the merger is on the order to of
several person-years for a vendor, that vendor might not survive the
change.  If there are such vendors, then the legal protections of CBEMA
for its members will be tested. 

In some cases, vendors may just decide not to support Common Lisp
and to go their own way if they feel that the changes make it no longer
an attractive or economical item to support.

Gabriel has estimated that at Lucid about 2~person-months are needed to
make the change initially followed by 4~person-months of shakedown.

Current estimates are that such change to the Symbolics Lisp environment 
would take much longer. Allowing proper time for quality assurance
and customer transition including backward compatibility, the process
could drag out for years. Symbolics does not believe that compatibility 
schemes such as those touched on in this paper are likely to offer any
significant aid in this process.

\ssect Can Users Afford the Merger?

Many users have a lot of Common Lisp code now. Symbolics users have just
undergone a major switchover from Zetalisp to Common Lisp. Even though
many of the changes are acknowledged by customers to be in their long
term best interest, they have found the transition to be painful. Part 
of the reason is that they were convinced that the change was worthwhile
by arguments that Common Lisp would remain fairly stable. If we pull the
rug out from under them with another major change, they may get pretty
nervous.

In the days of informally supported Lisps being distributed by universities,
we might have considered simply having a flag day after which things would
behave differently and have everyone simply agree to take the headache 
for the sake of some nebulous general good. Now that customers have invested
large amounts of money and perhaps entire businesses in products that depend
on the exact workings of Common Lisp, it is not likely to be so easy to
convince them to change.

Again, perhaps X3 can help by conditioning users for the switchover, and
perhaps DARPA can pay for tools to help users; for example, a codewalker
could be written that could used to parse files and to report places in
the code that require attention. However, for some customers, even this
might be too much work, too great an expense, or too impractical---too
impractical in light of existing product distribution schedules.

\sect Summary

There are compelling technical and non-technical reasons on both sides
of the issue. This white paper is an attempt to outline them so that
an informed decision can be reached.

\sect Acknowledgments

The authors gratefully acknowledge useful commentary and support of 
Will Clinger,
Scott Fahlman, 
and
David Moon.
\sect References

\makeref:Abelson.1985.{H. Abelson and G.J. Sussman with J. Sussman,
\book{Structure and Interpretation of Computer Programs}, The MIT Press,
Cambridge, Massachusetts, 1985.}

\makeref:Brooks.1982.{R.A. Brooks, R.P. Gabriel, and G.L. Steele, Jr.,
\article{S-1 Common Lisp
Implementation}, Proceedings of the 1982 ACM Symposium on Lisp and Functional 
Programming, Pittsburgh, PA, August 1982.}

\makeref:Digital.1986.{Digital Equipment Corporation, 
\book{VAX LISP/VMS User's Guide},
Maynard, MA, 1986.}

\makeref:Kohlbecker.1986.{E.E. Kohlbecker, Jr., \book{Syntactic Extensions in the 
Programming Language Lisp}, PhD thesis, Indiana University, August 1986.}

\makeref:Lucid.1986.{Lucid, Inc., \book{Lucid Common Lisp Reference Manual for
the VAX}, Menlo Park, CA, 1986.}

\makeref:McCarthy.1965.{J. McCarthy, et al, \book{Lisp 1.5 Programmer's Manual},
The MIT Press, Cambridge, Massachusetts, 1965.}

\makeref:Padget.1986.{J. Padget, et al, \article{Desiderata for the standardisation
of LISP}, Proceedings of the 1986 ACM Conference on Lisp and Functional 
Programming, Cambridge, MA, August 1986.}

\makeref:Pitman.1983.{K.M. Pitman, \book{The Revised Maclisp Manual} (Saturday
Evening Edition), LCS Technical Report 295, MIT, May 1983.}

\makeref:Rees.1986.{J. Rees and W. Clinger, editors, \book{$\hbox{Revised}↑3$
Report on the Algorithmic Language Scheme}, SIGPLAN Notices 21(12),
September 1986.}

\makeref:Steele.1984.{G.L. Steele Jr., \book{Common Lisp, The Language}, 
Digital Press, Billerica, Massachusetts, 1984.}

\makeref:Steele.1986.{G.L. Steele Jr. and W.D. Hillis, \book{Connection
$\hbox{Machine}↑\copyright$ Lisp: Fine-Grained Parallel Symbolic Processing},
Proceedings of the 1986 ACM Conference on Lisp and Functional
Programming, Cambridge, MA, August 1986.}

\makeref:Sussman.1975.{G.J. Sussman and G.L. Steele Jr.,
\book{SCHEME: An Interpreter
for Extended Lambda Calculus}, AI Memo 349, MIT, Cambridge, MA, December 1975.}

\makeref:Symbolics.1986a.{Symbolics, Inc., \book{MACSYMA Reference Manual},
Cambridge, MA, 1986.}

\makeref:Symbolics.1986b.{Symbolics, Inc., \book{Symbolics Common Lisp:
Language Concepts}, {\it Encyclopedia Symbolica}, Volume 2A, pp296-7,
Cambridge, MA 1986.}

\bye